//package work.rightAnswer;
//
//import work.ListNode;
//
//class Solution_86 {
//    public ListNode partition(ListNode head, int x) {
//        //创建两个头节点，分别记录小于x的节点和大于等于x的节点
//        //定义四个变量 ltHead 小于头节点 gtHead 大于头节点 ltTail小于尾节点 gtTail 大于尾节点
//        //还定义一个遍历变量 cur
//        //当遍历到小于x的节点时，tmp = cur.next ,cur.next=null;ltTail.next=cur;ltTail=cur;cur=temp;
//        //当遍历到大于等于x的节点时else tmp = cur.next ,cur.next=null;gtTail.next=cur;gtTail=cur;cur=temp;
//        ListNode ltHead = new ListNode();
//        ListNode gtHead = new ListNode();
//        ListNode ltTail = ltHead;
//        ListNode gtTail = gtHead;
//        ListNode cur = head;
//        while (cur!=null){
//            ListNode tmp = cur.next;
//            cur.next = null;
//            if(cur.val<x){
//                if(ltHead.next==null){
//                    ltHead.next = cur;
//                }
//                ltTail.next = cur;
//                ltTail = cur;
//            }else {
//                if(gtHead.next==null){
//                    gtHead.next = cur;
//                }
//                gtTail.next = cur;
//                gtTail = cur;
//            }
//            cur = tmp;
//        }
//
//        ltTail.next = gtHead.next;
//        gtHead.next = null;
//        return ltHead.next;
//    }
//}